package org.cxy.sort;

import java.util.Arrays;

// 快速排序
public class QuickSortDemo {
    public static void main(String[] args) {
        int[] arr = {25, 12, 20, 31, 8, 46, 15, 4, 50, 10};
        
        System.out.println("原始数组: " + Arrays.toString(arr));
        
        quickSort(arr, 0, arr.length - 1);
        
        System.out.println("排序后数组: " + Arrays.toString(arr));
    }

    /**
     * 快速排序主方法
     * 使用递归实现分治策略
     *
     * @param arr 待排序数组
     * @param leftIndex  当前子数组左边界
     * @param rightIndex 当前子数组右边界
     */
    public static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        // 递归终止条件：左边界大于右边界（说明子数组为空或只有一个元素）
        if (leftIndex >= rightIndex) {
            return;
        }

        int left = leftIndex;
        int right = rightIndex;
        int key = arr[left]; // 选取最左边元素作为基准值（pivot）

        System.out.println("当前排序区间 [" + leftIndex + ", " + rightIndex + "], 基准值: " + key);

        // 双指针扫描：left 从左往右，right 从右往左
        while (left < right) {
            // right 指针从右往左，找到第一个 < key 的元素
            while (right > left && arr[right] >= key) {
                right--;
            }
            // 将较小的元素放到左边空位（此时 arr[left] 是空的）
            arr[left] = arr[right];

            // left 指针从左往右，找到第一个 > key 的元素
            while (left < right && arr[left] <= key) {
                left++;
            }
            // 将较大的元素放到右边空位（此时 arr[right] 是空的）
            arr[right] = arr[left];
        }

        // ⚠️ 此时 left == right，该位置是基准值的最终位置
        // 将基准值放入该位置
        arr[left] = key;

        System.out.println("基准值 " + key + " 归位，当前数组: " + Arrays.toString(arr));

        // 递归排序基准值左边的子数组
        quickSort(arr, leftIndex, left - 1);
        // 递归排序基准值右边的子数组
        quickSort(arr, right + 1, rightIndex);
    }
}